package com.alibaba.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: dfs ,
 * 题目分析：
 * 从每一个点出发 , 走到与自己同等级的点 , 记录最短的距离
 * 以双向图存储数据
 *
 * 5
 * 1 2 3 2 1
 * 1 2
 * 2 3
 * 3 4
 * 4 5
 * @date 2021/07/02
 */

public class One_ShortestChainOnTheTree {

    private int root; // 全局根节点 , 依次将每个城市作为根节点 , 查找与自己同等级城市最近的距离
    private int ans = Integer.MAX_VALUE ; // 记录任意两个城市间最短链路
    private HashMap<Integer , ArrayList<Integer>> graph; // 双向图
    private int[] rank; // 每个城市等级

    public One_ShortestChainOnTheTree(HashMap<Integer , ArrayList<Integer>> graph , int[] rank){
        this.graph = graph;
        this.rank = rank;
    }

    public int getShortestChainOnTheTree(){
        int len = rank.length - 1;
        for(int i = 1 ; i <= len ; i ++){
            this.root = i; // 将每个节点作为根节点 , 并记录所有结果中最小值
            dfs(root , 0 , 0);
        }
        return ans;
    }

    public void dfs(int cur , int pre , int deep){
        if(cur != root && rank[cur] == rank[root]){ // 当前不是根节点 , 但是与根节点同等级 , 此时需要记录最小的链路距离 , ( 因为一个节点可能与多个城市属于同级 )
            ans = Math.min(ans , deep);
        }
        for(int city : graph.get(cur)){
            if(city != pre){ // 回头了 , 因为是双向图 ,
                dfs(city , cur , deep + 1);
            }
        }
    }

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] rank = new int[n + 1];
        for(int i = 1 ; i <= n ; i ++){
            rank[i] = input.nextInt();
        }
        HashMap<Integer , ArrayList<Integer>> graph = new HashMap<>();
        // 构建数据 , 并进行处理了 , 即构建双向图
        for(int i = 1 ; i < n ; i ++){
            int city1 = input.nextInt();
            int city2 = input.nextInt();
            ArrayList<Integer> temp =  graph.containsKey(city1) ? graph.get(city1) : new ArrayList<>();
            temp.add(city2);
            graph.put(city1 , temp);
            ArrayList<Integer> temp2 = graph.containsKey(city2) ? graph.get(city2) : new ArrayList<>();
            temp2.add(city1);
            graph.put(city2 , temp2);
        }

        One_ShortestChainOnTheTree tree = new One_ShortestChainOnTheTree(graph , rank);
        System.out.println(tree.getShortestChainOnTheTree());
    }

}
